//https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-100-liked
//贪心思想：这样以来，我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置x，如果它在最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x+nums[x] 更新 最远可以到达的位置。
//回溯法：也是非常好的想法；
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if (nums.empty()) {
            return false;
        }
        int k=0;
        for (int i = 0; i <= k; i++) {
            //第i个元素能够跳到的最远距离
            int temp = i + nums[i];
            //更新最远距离
            k = std::max(k, temp);
            //如果最远距离已经大于或等于最后一个元素的下标,则说明能跳过去,退出. 减少循环
            if (k >= nums.size() - 1) {
                return true;
            }
        }
        //最远距离k不再改变,且没有到末尾元素
        return false;
    }
};

//回溯法
class Solution2 {
    bool backTracking(vector<int>& nums, int i) {
        if (i + nums[i] >= static_cast<int>(nums.size()) - 1) return true; // static_cast<int> - 因为需要用unsigned - 1，转换成int比较保险，否则0 - 1会溢出
        // if (!nums[i]) return false; // 添加这句可以通过test case1，但是另一个不行
        for (int j = nums[i]; j > 0; j--) if (backTracking(nums, j + i)) return true;
        return false;
    }

public:
    bool canJump(vector<int>& nums) { return backTracking(nums, 0); }
};